package p206;

import node.ListNode;
import node.ListNodeManager;

/**
 * <pre>
 *  206. 反转链表
 * 反转一个单链表。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * 进阶:
 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 *
 * 通过次数380,791提交次数536,103
 * </pre>
 */
public class Solution {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        ListNode root = ListNodeManager.createListNodeByArray(nums);
        ListNode t = reverseList(root);
        ListNodeManager.printlnNode(t);
    }

    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode root = head;
        while (root != null) {
            ListNode cur = root.next;
            System.out.println("root" + root.val);

            //change
            root.next = pre;
            pre = root;

            root = cur;
        }
        return pre;
    }

    /**
     *<pre>
     * 方法二：递归
     * 递归版本稍微复杂一些，其关键在于反向工作。假设列表的其余部分已经被反转，现在我们应该如何反转它前面的部分？
     *
     * n1 →…→nk−1 →nk →nk+1 →…→nm →∅
     *
     * 若从节点 n_{k+1}nk+1到 n_{m}nm
     *
     * 已经被反转，而我们正处于 n_{k}nk
     *
     * n1 →…→ nk−1 → nk → nk+1 ←… ←nm
     *
     * 我们希望 n_{k+1}nk+1的下一个节点指向 n_{k}nk
     *
     * 所以，nk.next.next=nk
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，假设 nn 是列表的长度，那么时间复杂度为 O(n)O(n)。
     * 空间复杂度：O(n)O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 nn 层。
     *
     *</pre>
     * @param head
     * @return
     */
//    public static ListNode reverseList(ListNode head) {
//        if (head == null || head.next == null)
//            return head;
//        ListNode tempt = reverseList(head.next);
//        head.next.next = head;
//        head.next = null;
//        return tempt;
//    }


}
